package algorithm.niuke;

/**
 * 链表问题
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-05-12
 */
public class LinkedListTest {

    public static void main(String[] args) {
        ListNode1 node1 = new ListNode1(1);
        ListNode1 node3 = new ListNode1(2);
        ListNode1 node4 = new ListNode1(3);
        node1.next = node3;
        node3.next = node4;

//        ListNode1 kthToTail = findKthToTail(node1, 1);
//        System.out.println(kthToTail);
        ListNode1 reverseHead = reverseList(node1);
        System.out.println(reverseHead);

    }

    /**
     * 输入一个链表，输出该链表中倒数第k个结点
     *
     * @param head 头节点
     * @param k    倒数第K节点索引
     * @return 第k个结点
     */
    private static ListNode1 findKthToTail(ListNode1 head, int k) {

        if (head == null || head.next == null) {
            return head;
        }

        int length = 0;
        ListNode1 node = head;
        while (node != null) {
            length += 1;
            node = node.next;
        }

        if (k > length) {
            return null;
        }
        int targetIndex = length - k;
        ListNode1 pre = head;
        for (int i = 0; i < targetIndex; i++) {
            pre = pre.next;
        }

        return pre;
    }

    /**
     * 反转链表
     *
     * @param head 头节点
     * @return 反转之后的链表
     */
    public static ListNode1 reverseList(ListNode1 head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode1 curNode = head;
        ListNode1 nextNode;
        ListNode1 reverseHead = new ListNode1(0);

        while (curNode != null) {
            nextNode = curNode.next;
            curNode.next = reverseHead.next;
            reverseHead.next = curNode;
            curNode = nextNode;
        }

        return reverseHead.next;

    }

    /**
     * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
     * 思路：比较两个链表的值，小的放前面，大的进入下一轮
     *
     * @param list1 链表1头节点
     * @param list2 链表2头结点
     * @return 合并之后的头结点
     */
    public ListNode1 merge(ListNode1 list1, ListNode1 list2) {

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        int val1 = list1.val;
        int val2 = list2.val;
        ListNode1 head;
        if (val1 < val2) {
            head = new ListNode1(val1);
            head.next = merge(list1.next, list2);
        } else {
            head = new ListNode1(val2);
            head.next = merge(list1, list2.next);
        }

        return head;
    }

    /**
     * 输入一个复杂链表，请对此链表进行深拷贝，并返回拷贝后的头结点。
     *
     * @param pHead 复杂链表头结点
     * @return 复制之后头结点
     */
    public RandomListNode clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode curNode = pHead;

        // 复制每个节点，然后把复制的节点连接到该节点后面
        while (curNode != null) {
            RandomListNode cloneNode = new RandomListNode(curNode.label);
            RandomListNode nextNode = curNode.next;
            curNode.next = cloneNode;
            cloneNode.next = nextNode;
            curNode = nextNode;
        }

        // 复制兄弟节点
        curNode = pHead;
        while (curNode != null) {
            curNode.next.random = curNode.random == null ? null : curNode.random.next;
            curNode = curNode.next.next;
        }

        curNode = pHead;
        RandomListNode cloneHead = pHead.next;
        while (curNode != null) {
            RandomListNode cNode = curNode.next;
            // 恢复原来链表
            curNode.next = cNode.next;
            // 复制的链表
            cNode.next = cNode.next == null ? null : cNode.next.next;
            curNode = curNode.next;
        }

        return cloneHead;

    }
}


class ListNode1 {
    int val;
    ListNode1 next = null;

    ListNode1(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode1{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
